package 回溯;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: shuai.chen@shuyun.com
 * @date: 2023/2/8 10:44 AM
 */
public class EightQueen2 {

    @Test
    public void test2(){
        solveNQueens(8);
        Assert.assertSame(92, list.size());
    }

    List<List<String>> list = new ArrayList<>();
    char[][] visited;

    public List<List<String>> solveNQueens(int n) {
        visited = new char[n][n];
        //填充visited数组为 '.'
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], '.');
        }
        dfs(n, 0);
        return list;
    }

    public void dfs(int n, int floor) {
        //floor == n，说明 0 ~ n-1 已经满足条件了
        if (floor == n) {
            ArrayList<String> temp = new ArrayList<>();
            for (int i = 0; i < visited.length; i++) {
                temp.add(new String(visited[i]));
            }
            list.add(temp);
            return;
        }
        //逐个判断当前位置是否可以放皇后，记得恢复原位
        for (int i = 0; i < n; i++) {
            if (isOk(floor, i)) {
                visited[floor][i] = 'Q'; // 变
                dfs(n, floor + 1); // 放下一行
                visited[floor][i] = '.'; // 恢复 （回溯）
            }
        }

    }

    public boolean isOk(int row, int col) {
        // 当前行 不用判断

        // 当前列
        for (int k = 0; k < row; k++) {
            // 列不变，行变化
            if (visited[k][col] == 'Q') {
                return false;
            }
        }

        // 两个对角线 如何判断呢？

        // 左上角找  (row-1, col-1)  (row-2, col-2)
        int row1 = row, col1 = col;
        while (row1 >= 0 && col1 >= 0) {
            if (visited[row1--][col1--] == 'Q') {
                return false;
            }
        }
        // 右上角 (row-1,col+1) (row-2,col+2)
        int row2 = row, col2 = col;
        while (row2 >= 0 && col2 < visited.length) {
            if (visited[row2--][col2++] == 'Q') {
                return false;
            }
        }

        return true;
    }

}

